HDU_5763

题解

对于这个问题，显然可以进行DP：
令dp[i]表示到i结尾的字符串可以表示的不同含义数，那么考虑两种转移:

末尾不替换含义：dp[i - 1]

末尾替换含义：dp[i - |B|] (A.substr(i - |B| + 1,|B|) = B)

那么对于末尾替换含义的转移，需要快速判断BB能不能和当前位置的后缀匹配，kmp或者hash判断即可。

复杂度:O(N)

Beyond说

这道题很简单，但是坑了我三个小时到最后都没过，我是很遗憾。该死的OJ一直说我Timelimits Out，导致我一直在算法和优化下下功夫……最后发现是自己把数组开小了，少打了一个零，改了后秒AC 555555——T_T
这道题是一道基础的dp，我的公式是：

dp[i]=dp[i-1]+dp[i-|B|];
条件是手动初始化dp[0]-dp[|B|]。

我没有用KMP算法，也就15MS过了。想必出题人没有恶心数据，比如50000 A 50000 B 且A B 串内有多重复字符，这样的话，估计又要死一片人。不过这道题考的是dp，如果那样，就是实在太过于恶心了。

c++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>  
#include <cstdio>
using namespace std;
#define inf 0x3f3f3f3f  
int const N = 1e5+5;
int a[N],sub[N],up[N];
int find(int *a,int len,int n)//若返回值为x,则a[x]>=n>a[x-1]  
{  
    int left=0,right=len,mid=(left+right)/2;  
    while(left<=right)  
    {  
        if(n>a[mid]) left=mid+1;  
        else if(n<a[mid]) right=mid-1;  
        else return mid;  
        mid=(left+right)/2;  
    }  
    return left;    
}  
       
void init(int *t,int n)  
{  
    for(int i=0;i<=n;i++)  
        t[i]=inf;  
    t[0]=-1;
    t[1]=a[0];
    sub[0]=1;
}  
       
int main()  
{  
    int max,i,j,n,t;  cin>>t;
    while(t--)  
    {        
        cin>>n;
        for(i=0;i<n;i++)  
            cin>>a[i]; 
        init(up,n+1);  
        for(i=1;i<n;i++)
        {  
            j=find(up,n+1,a[i]);
            up[j]=a[i];
            sub[i]=j; 
        }  
        for(int i=0;i<n;i++)
            printf("%d%c",sub[i],i==n-1?'\n':' ');
    }  
    return 0;  
}